/**
 * @file   a_star.h
 * @brief  a star头文件
 * @encode UTF-8
 * @log    date        author      notes
 *         2021.09.01  Jimmy       first version
 */
#ifndef __A_STAR_H_ 
#define __A_STAR_H_ 

#include <vector>
#include <memory>
#include <algorithm>
#include <cstring>
#include <thread>
#include <iostream>

#include "utils/maps.h"

namespace a_star
{
    enum astar_status_t
    {
        ASS_NULL = 0,
        ASS_OK,
        ASS_WAIT,
        ASS_NOT_FOUND,
        ASS_START_TRAP,
        ASS_END_TRAP
    };
}

struct AStarPoint
{
    Point pos;
    int f = 0;  /* 从起点到终点的计算成本 */
    int g = 0;  /* 起点到当前点的累加成本 */
    int h = 0;  /* 当前点到终点的预计成本 */
};


class AStar
{
    public:
        class greater_class
        {
            public:
                bool operator()(AStarPoint & a, AStarPoint & b)
                {
                    return (a.f > b.f);
                }
        };

        class Heap
        {
            private:
                std::vector<AStarPoint> mList;
            public:
                Heap()
                {
                    mList.clear();
                    make_heap(mList.begin(), mList.end(), greater_class());
                }

                ~Heap()
                {
                    mList.clear();
                }

                void clear()
                {
                    mList.clear();
                }

                void push(AStarPoint point)
                {
                    mList.push_back(point);
                    push_heap(mList.begin(), mList.end(), greater_class());
                }

                AStarPoint popMin()
                {
                    pop_heap(mList.begin(), mList.end(), greater_class());
                    AStarPoint node = mList.back();
                    mList.pop_back();
                    return node;
                }

                int size(void)
                {
                    return (int)(mList.size());
                }

                bool isEmpty(void)
                {
                    return (mList.empty());
                }

        };

        class CloseList
        {
            public:
                enum add_rst_t
                {
                    CLR_NULL    = 0,
                    CLR_SUCCESS = CLR_NULL,
                    CLR_CLOSED,
                    CLR_TRAVERSED,
                };
            private:
                std::vector<uint8_t> mList;
                uint16_t mWidth;
                uint16_t mHeight;
                uint16_t mCloseSize;

            public:
                CloseList()
                {
                    mList.clear();
                    mWidth = mHeight = 0;
                    mCloseSize = 0;
                }

                ~CloseList()
                {
                    
                }

                void init(uint16_t width, uint16_t height)
                {
                    mCloseSize = 0;
                    mWidth  = width;
                    mHeight = height;
                    unsigned int mapSize = width * height;
                    mList.resize(mapSize, 0);    

                    for (int i = 0; i < mWidth; i ++)
                    {
                        mList[i] = 3;
                        mList[mWidth * mHeight - i - 1] = 3;
                    }   

                    for (int j = 0; j < mHeight; j ++)
                    {
                        mList[j * mWidth] = 3;
                        mList[(j + 1) * mWidth - 1] = 3;
                    }
                }

                add_rst_t addToList(uint8_t dxdyNum, uint8_t index, Point point)
                {
                    int temp = point.y * mWidth + point.x;

                    if (!mList[temp])
                    {
                        mCloseSize ++;
                        mList[temp] = (dxdyNum << 4) + index;
                        return CLR_SUCCESS;     /* 插入成功 */
                    }

                    if ((mList[temp] & 0x0F) + index == 3)
                    {
                        return CLR_CLOSED;      /* 闭合 */
                    }
                    else 
                    {
                        return CLR_TRAVERSED;   /* 遍历过该点 */
                    }
                }

                /* 高4位记录上一点的遍历方向，后4位标记点的属性，如终点或起点遍历到的范围 */
                uint8_t getIndex(Point & point)
                {
                    return (uint8_t)(mList[point.y * mWidth + point.x] & 0x0F);
                }

                uint8_t getDxDy(Point & point)
                {
                    return (uint8_t)(mList[point.y * mWidth + point.x] >> 4);
                }

                bool isClose(Point & point)
                {
                    return (mList[point.y * mWidth + point.x] != 0);
                }

                uint16_t getCloseCount(void)
                {
                    return mCloseSize;
                }
        };

    public:
        AStar();
        ~AStar();

        void updateMap(const MapData & mapData);
        void updateMap(const MapData & mapData, uint16_t width, uint16_t height, int xMin, int yMin, int xMax, int yMax, bool do_erode);
        a_star::astar_status_t pathing(Point & start, Point & dest, std::vector<Point> & path);
        a_star::astar_status_t pathingWithSingle(Point & start, Point & dest, std::vector<Point> & path);
        a_star::astar_status_t pathingWithNormal(Point & start, Point & dest, std::vector<Point> & path);

    private:
        std::unique_ptr<Heap> mStartOpen;
        std::unique_ptr<Heap> mEndOpen;
        std::unique_ptr<CloseList> mClose;

        uint16_t mWidth;
        uint16_t mHeight;
        uint16_t mMapSize;

        // uint8_t * mMapByte = nullptr;
        std::vector<uint8_t> mMapByte;

        Point mObstaclePoint;

    private:
        uint8_t calcH(Point & n_point, Point & dest_point);

        bool canPass(Point & point, uint8_t ref);
        bool isPointIn(Point & point, Point & minPoint, Point & maxPoint);
        bool pointIsCanJump(Point p1, Point p2, uint8_t ref);

};


#endif	/* __A_STAR_H_ */

